//https://leetcode.cn/problems/house-robber-ii/

class Solution {
public:
    int rob(vector<int>& nums) {
        return max(nums[0] + rob1(2, nums.size() - 2, nums), rob1(1, nums.size() - 1, nums));

    }

    int rob1(int n, int m, vector<int> nums)
    {
        if (n > m) return 0;
        vector<int> dpf(nums.size());
        vector<int> dpg(nums.size());

        dpf[n] = nums[n];
        for (int i = n + 1; i <= m; i++)
        {
            dpf[i] = dpg[i - 1] + nums[i];
            dpg[i] = max(dpf[i - 1], dpg[i - 1]);
        }

        return max(dpf[m], dpg[m]);
    }
};